COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00012 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\let\phi=\varphi
\baselineskip 14pt
\leftline{\sevenrm A90.Tex[254,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 19, 0989}
\leftline{\sevenrm Unpublished draft}
\bigskip
A relation $\sigma$ is {\it concatenative} if $x↓1\sigma y↓1$ and $x↓2\sigma y↓2$ 
implies $(x↓1x↓2)\sigma (y↓1y↓2)$.

Let $\rho$ be a finite relation on $\sum↑*$.  An element $\langle x↓1y\rangle$ 
of $\rho$ is called a {\it production}.  (Commonly $x\rightarrow y$ is written to
indicate $x\rho y$.)  Let $\tilde\rho$ be the least relation for which
$x\rho y$ implies $uxv \,\tilde\rho\, uyv$.  That is, $w \tilde\rho z$ if
replacing $x$ by $y$ somewhere in $w$ changes it to $z$.  Then $\tilde\rho↑*$
is the least relation that contains $\rho$, is reflexive, transitive, and
concatenative.  (Commonly $x\Rightarrow y$ is written to indicate $x\tilde\rho
y$, and $x\Rightarrow↑\ast y$ is written to indicate 
$x \tilde\rho↑* y)$.  That is,
$u \tilde\rho↑* v$ if $u$ can be changed into $v$ by a sequence of
steps where some occurrence of $x$ is replaced by $y$, with $x\rho y$.  The
relation $\tilde\rho↑*$ is called a {\it semi-Thue system} or STS.

If $\sigma =\rho\cup\rho↑{-1}$, the symmetric closure of $\rho$, then $\tilde
\sigma↑*$ is symmetric, and in fact is an equivalence relation, called a
{\it Thue system} (pronounced ``two-way'', appropriately), a special case of
an STS.  It is the smallest concatenative equivalence relation containing
$\rho$.

The {\it word problem} of $u$ and $v$ for an STS is the problem whether
$u \tilde\rho↑* v$, i.e. whether $u$ can be changed into $v$ by repeatedly
rewriting using productions of $\rho$.  The halting problem for oblivious TMs
can be reduced to the word problem for an STS, and even for a Thue system, so
the general word problem is undecidable.

Take a halting problem for a TM consisting of a right stack, a finite control,
and a left stack.  The configuration $\langle x, q, y\rangle$ can be
represented by the string $sqy$.  We construct an STS, $\rho$, such that
$\langle x↓1, q↓1, y↓1\rangle \pi \langle x↓2, q↓2, y↓2\rangle$ iff
$x↓1 q↓1 y↓1 \,\tilde\rho\, x↓2\, q↓2\, y↓2$.  Corresponding to each instruction
of the TM in the left column below we include the corresponding production
in the right column.
$$\vbox{\halign{$#$\hfill &\qquad $#$ \hfill\cr
\langle{\rm push\, a}, q\rightarrow r, {\rm noop}\rangle & q\rightarrow ar\cr
\langle{\rm pop\, a}, q\rightarrow r,{\rm noop}\rangle & aq\rightarrow r\cr
\langle{\rm noop}, q\rightarrow r, {\rm push\, b}\rangle & q\rightarrow rb\cr
\langle{\rm noop}, q\rightarrow r, {\rm pop\, b}\rangle & qb\rightarrow r\cr}}$$
For example, the first line gives the corresponding relations $\langle x, q,
y\rangle\pi\langle xa, r, y\rangle and xqy \,\tilde\rho\, xary$.

Naturally, $\langle x↓1, q↓1, y↓1\rangle\pi↑*\langle x↓2, q↓2, y↓2\rangle$
iff $(x↓1, q↓1, y↓1)\tilde\rho↑* \langle x↓2\, q↓2\, y↓2\rangle$.  
The halting problem of 
determining whether $\langle\Lambda, q↓\alpha,\Lambda\rangle\pi↑*\langle
\Lambda, q↓\omega, \Lambda\rangle$ then reduces to the word problem
$q↓\alpha \,\tilde\rho↑* q↓\omega$, which is therefore generally undecidable.

{\narrower\smallskip\noindent
{\bf Exercise:}  Show that the word problem is decidable for an STS where
$x\rho y$ implies $\left | x\left | \leq \right | y\right |$.\smallskip}

{\narrower\smallskip\noindent
{\bf Exercise:}  Let $f$ be any computable function from strings to natural
numbers.  Show that the word problem is decidable if $x \tilde\rho y$ implies
$f(x) < f(y)$.\smallskip}

To show that word problems of Thue systems are also generally undecidable, we 
construct a halting problem $\langle\Lambda, q↓\alpha, 
\Lambda\rangle\pi↑*\langle\Lambda, q↓\omega,\Lambda\rangle$
for a deterministic program, where $\langle\Lambda, q↓\omega,\Lambda\rangle\circ
\pi = \emptyset$.  This is an easy transformation on the general halting 
problem for an oblivious two-stack Turing machine.  Now we take the set of 
productions $\rho$ as before, set $\sigma = \rho\cup\rho↑{-1}$, and pose the
word problem $q↓\alpha \,\tilde\sigma↑* q↓\omega$.  Allowing the productions
to be applied in reverse is equivalent to letting the program take backward 
steps.  It turns out that adding backward steps to a deterministic program 
is not helpful in reaching a terminal configuration.

Let $\phi$ be a partial function (i.e. a functional relation); then $\phi↑{-1}
\circ\phi\subset\delta$.  Let $A$ and $B$ be sets, with $B\circ\phi = \emptyset$.
We show that $\phi↑*\circ B = (\phi\cup\phi↑{-1})↑*\circ B$, and therefore
$A\circ\phi↑*\circ B$ iff $A\circ (\phi\cup\phi↑{-1})↑*\circ B$.

First, we show by induction that $(\phi\cup\phi↑{-1})↑n\subset\phi↑*\phi↑{-*}$.
$$\eqalign{& (\phi\cup\phi↑{-1})↑{n+1}\cr
&\qquad = (\phi\cup\phi↑{-1})(\phi\cup\phi↑{-1})↑n\subset (\phi\cup\phi↑{-1})
\phi↑*\phi{↑-*}\cr
&\qquad = \phi \,\phi↑*\phi↑{-*}\cup\phi↑{-1} (\delta\cup\phi \,\phi↑*)
\phi↑{-*}\cr
&\qquad = \phi \,\phi↑*\phi↑{-*}\cup\phi↑{-1}\delta\phi↑{-*}\cup\phi↑{-1}
\phi \,\phi↑*\phi↑{-*}\cr
&\qquad\subset\phi↑*\phi↑{-*}\cup\phi↑{-*}\cup\delta\phi↑*\phi↑{-*}\cr
&\qquad = \phi↑*\phi↑{-*}.\cr}$$
So $(\phi\cup\phi↑{-1})↑*\subset\phi↑*\phi↑{-*}$.  Then
$$\eqalign{& (\phi\cup\phi↑{-1})↑*\circ B\subset\phi↑*\circ\phi↑{-*}
\circ B\cr
&\qquad = \phi↑*\circ (\phi↑{-*}\phi↑{-1}\cup\delta )\circ B\cr
&\qquad = \phi↑*\circ (\phi↑{-*}\circ\phi↑{-1}\circ B\cup\delta\circ B)\cr
&\qquad = \phi↑*\circ (B\circ\phi\circ\phi↑*\cup B)\cr
&\qquad = \phi↑*\circ (\emptyset\cup B)\cr
&\qquad = \phi↑*\circ B.\cr}$$
The argument, in words, is this.  Take the shortest sequence of application of
$\tilde\rho$ and $\tilde\rho↑{-1}$ that takes $q↓\alpha$ to $q↓\omega$.
Applying $\tilde\rho↑{-1}$ and then $\tilde\rho$ has no net effect because
$\tilde\rho$ is functional, so the sequence must be of the form
$\tilde\rho↑a \tilde\rho↑{-b}$.  If any $x \tilde\rho↑{-1} q↓\omega$, we
would have $q↓\omega\, \tilde\rho\, x$, and $\langle\Lambda, q↓\omega, \Lambda
\rangle$ would not be a terminal configuration.  Then the sequence must be of the
form $\tilde\rho↑a$, so $q↓\alpha (\tilde\rho\cup\tilde\rho↑{-1})↑* q↓\omega$
only if $q↓\alpha \,\tilde\rho↑* \,q↓\omega$.
\bye